#include <iostream>
#include <string.h>
using namespace std;
const int SIZE =100;
char  src[SIZE]="ababaca";
char des[SIZE] ="bacbababaababacammk";
int  next[SIZE];
void getnext();
void shownext();
int find();
int main()
{
    //cout << "Hello world!" << endl;
    getnext();
    shownext();
    int st = find();
    int len=strlen(src);
    cout<<"find src start from:"<<st<<endl;
    for (int i=st;(i-st)<len;i++){
        printf("%c",des[i]);
    }
    printf("\n");
    return 0;
}
int find(){
    int lsrc=strlen(src);
    int ldes=strlen(des);
    int i,j;
    j=-1;
    for (i=0;i<ldes;i++){
        while (j>=0 && src[j+1]!=des[i]){
            j=next[j];
        }
        if (src[j+1]==des[i]){
            j++;
        }
        if (j+1==lsrc){
            return (i-lsrc+1);
        }
    }
    return i;
}
void getnext(){
    int i,j;
    i=1;
    j=-1;
    next[0]=-1;
    int len =  strlen(src);
    for (i=1;i<len;i++){
        while (j>=0 && src[j+1]!=src[i]){
            j=next[j];
        }
        if (src[j+1]==src[i])
            j++;
        next[i]=j;
    }
}
void shownext(){
    cout<<"next"<<endl;
    int i=0;
    int len = strlen(src);
    for (i=0 ; i<len;i++){
        printf("%c   ",src[i]);
    }
    printf("\n");
    for (i=0;i<len;i++){
        printf("%d  ",next[i]);
    }
    printf("\n");
}
